Mesh networking can be defined as a way to route data, voice and instructions between nodes. It allows for continuous connections and reconfiguration around broken or blocked paths by “hopping” from node to node until the destination is reached. A mesh network whose nodes are all connected to each other is a fully connected network. Mesh networks differ from other networks in that the component parts can all connect to each other via multiple hops, and they generally are not mobile. Mesh networks can be seen as one type of ad hoc network.
A node is a critical element of any computer network. It can be defined as a point in a network at which lines intersect or branch, a device attached to a network, or a terminal or other point in a computer network where messages can be created, received, or transmitted. A node can be any device connected to a computer network. Nodes can be computers, personal digital assistants (PDAs), cell phones, or various other networked devices. On a TCP/IP network, a node is any device with an IP address. If the node is a computer, it is more often called a “host”. A node is a connection point, either a redistribution point or an end point, for data transmission. In general, a node has programmed or engineered capability to recognize and process or forward transmissions to other nodes. If the network in question is the Internet, every node must have a MAC address or Data Link Control address if it is at least a data link layer device, as defined in the OSI model.
Routing algorithms for mesh network have to be robust to node failures, and link quality variations due to packet loss, and shadow-fading. It has been shown in the scientific publication “Performance Anomaly of 802.11 b” (M. Heusse, F. Rousseau, G. Berger-Sabbatel, A. Duda, in proc. of IEEE Infocom 2003, San Francisco, Calif., USA, March 2003) that the MAC-layer interactions play a significant role in determining the capacity of a link. The MAC-layer is the Media Access Control layer that arbitrates access of nodes to the wireless medium. In particular, depending on the MAC-layer contention, the goodput of a link can be substantially lower than its bit rate due to sharing of the wireless medium by multiple nodes. Past work has primarily focused on defining routing metrics to determine high throughput routes. Examples of such routing metrics are MAC-agnostic routing metrics, such as ETX [D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris, “A High-Throughput Path Metric for Multi-Hop Wireless Routing” in proc. of ACM MobiCom 2003, San Diego, Calif., USA, Sep 2003], ETT [J. Padhye, R. Draves, and B. Zill, “Routing in Multi-radio, Multi-hop Wireless Mesh Networks” in proc. of ACM MobiCom 2004, Philadelphia, Pennsylvania, USA, Sep 2004], and MAC-aware routing metrics, such as ETP [V. Mhatre, H. Lundgren, and C. Diot. Mac-aware routing in wireless mesh networks. In The Fourth International Wireless on Demand Network Systems and Services (IEEE/IFIP WONS 2007), Obergurgl, Austria, January 2007], EDR [J. C. Park and S. Kasera, “Expected Data Rate: An Accurate High-Throughput Path Metric For Multi-Hop Wireless Routing” in proc. of IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, SECON 2005, Santa Clara, Calif., USA, Sep 2005], IRU [Y. Yang, J. Wang, and R. Kravets, “Designing Routing Metrics for Mesh Networks” in proc. of IEEE Workshop on Wireless Mesh Networks WiMesh 2005, Santa Clara, Calif., USA, Sep 2005].
When shortest path routing is used with any of the above routing metrics, the resulting routing algorithms do not support load balancing. This is because the load-agnostic behavior of shortest path algorithms can result in scenarios where a few gateways have too many associated mesh nodes, while other gateways are under-utilized. Further load imbalance in the network could be caused by gateway failures. 100% uptime for gateways is not possible, since the connection of the gateways to the Internet may fail occasionally, or the gateways may be unreachable [http://www.netequality.net]. Consequently, failure of one or more gateways can lead to overloading of a few selected gateways. Load balancing and routing algorithms which recently proposed in [Y. Bejerano, S. Han, and A. Kumar, “Efficient load-balancing routing for wireless mesh networks” Computer Networks, Elsevier Science, 2007, Vol. 51, pp 2450-2466] to handle such load imbalance do not take the MAC-layer interaction into account.